不妨设 , 且$ n < m $。
回忆一下卡塔兰数的推导过程 ， 我们用类似的方法解决此题。
CF999E Reachability from the Capital
显然，在一个强联通分量中，只要有一个城市与s联通，那么整个分量就与s联通。
于是我们可以缩点，统计它的入度。如果入度为0，我们就从s向这个缩点连一条边，如果入度不为0，说明其他城市可以到达它，我们就不需要单独连边。
最后，注意特判与s在同一强联通分量的点。
P1829 [国家集训队]Crash的数字表格
i=1∑nj=1∑mlcm(i,j)
P2831 愤怒的小鸟
首先，我们得知道过原点与两点的抛物线解析式：
设该函数解析式为 y=ax2+bx+c(a<0)且过 (0,0),(x1,y1),(x2,y2) 三点。
由函数过 (0,0) 得 c=0。
P4778 Counting swaps
对于每个位置 i , 我们向 pi 连一条边。 结合题意可知，一个合法的排列，是一个由 n 个自环组成的图。
但现在会形成多个环，不妨记环的数量为 k ， 第 i 个环的大小为 si（包括自环）。
我们现在要做的，就是将这 k 个环拆成 n 个自环。
SP694 DISUBSTR - Distinct Substrings
这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 ， 我们就可以在 DAWG 上 dp 。 dp[u]表示包含转移u的子串数量，很容易列出转移式：
SP1811 LCS - Longest Common Substring
一道后缀自动机的板题。
我们从根结点开始匹配，如果有转移就将cnt++
不然就顺着后缀链接向上跳，直到找到有转移的点，用 Maxlen 继续匹配。(后缀链接一定是它的子串，也能被匹配)。
0%